Usuwanka

Limit pamięci: 64 MB

Mała Bajtosia dostała w prezencie grę o nazwie Usuwanka. W tej grze dany jest ciąg przylegających do siebie klocków, ponumerowanych kolejno od 1 do . Każdy klocek jest albo biały, albo czarny, przy czym białych klocków jest razy więcej niż czarnych. Gra jest jednoosobowa. Celem gry jest usunięcie, za pomocą określonych ruchów, wszystkich klocków z ciągu.

Pojedynczy ruch polega na usunięciu dokładnie białych i jednego czarnego klocka bez zmiany pozycji pozostałych klocków. Ruch jest dozwolony, jeśli między żadnymi dwoma usuwanymi w tym ruchu klockami nie ma "dziury", czyli pustego miejsca po uprzednio usuniętym klocku.

Pomóż Bajtosi, ona tak bardzo Cię prosi... Znajdź dowolny ciąg dozwolonych ruchów prowadzący do usunięcia wszystkich klocków.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem, oznaczające liczbę klocków w grze oraz liczbę białych klocków, które należy usunąć w każdym ruchu. We wszystkich testach zachodzi warunek .

W drugim wierszu znajduje się napis złożony z liter b oraz c. Kolejne litery napisu określają kolor kolejnych klocków: b - biały, c - czarny. Możesz założyć, że dla danych testowych istnieje szukany ciąg ruchów prowadzący do usunięcia wszystkich klocków.

W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. Kolejne wiersze powinny opisywać kolejne ruchy. Każdy z tych wierszy powinien zawierać liczb, podanych w kolejności rosnącej oraz rozdzielonych pojedynczymi odstępami, oznaczających numery klocków, które należy usunąć w danym ruchu.

Przykład

Dla danych wejściowych:

12 2
ccbcbbbbbbcb

poprawną odpowiedzią jest:

1 8 12
2 6 7
3 4 5
9 10 11

Wyjaśnienie do przykładu: Niech oznacza puste miejsce po usuniętym klocku. Wykonując podane powyżej ruchy, uzyskujemy kolejno następujące układy klocków:

Autorzy zadania: Jakub Pachocki, Wojciech Rytter.